iT邦幫忙

2021 iThome 鐵人賽

DAY 22
1
Software Development

少女人妻在廚房裡想不通的演算法系列 第 22

【在廚房想30天的演算法】Day 22 演算法 : 最短路徑 Shortest Path Bellman–Ford 演算法

  • 分享至 

  • xImage
  •  

Aloha!我是少女人妻 Uerica!我家狗狗每天六點都會叫我起床,但除非自己很早睡,不然六點起床實在很崩潰啊,而且她看我下床就跑回去睡回籠覺(!?),所以剛剛趁她回去睡覺時偷偷在我家客廳的瑜珈墊上假裝躺著冥想,結果沒一陣子就聽到急促的腳步聲“噠噠噠噠噠”,然後一隻狗站在我正前方,下一秒就是用腳掌巴我,巴到我坐在電腦前寫文章為止QQ


好喔大家早安,今天要繼續説說最短路徑的演算法啦~還記得昨天的達克斯特拉的演算法是不能用在負權重上嗎~所以就出現了另一個改良版,叫做貝爾曼福特演算法!

貝爾曼-福特演算法 Bellman–Ford algorithm

貝爾曼福特演算法與達克斯特拉演算法的不同處在於,貝爾曼福特演算法是用Label Correcting 的方式,簡單來說就是整個過程不斷修改路徑的權重,以找到最短路徑的方式,所以適用於有負數邊的情形,而達克斯特拉演算法則是使用 Label Setting 的方式,也就是逐一的選擇權重較小的邊來做延伸。

  • 不可有長度為負數的環 (cycle)
  • 從起點到所有點的最短路徑,若有 n 個點,那最短路徑則是 n-1 個邊 ,若超過 n-1 個邊,就可能有負數的環

Bellman–Ford algorithm 圖解

  • 延續昨天的話題,因為疫情剛結束降至二級,有兩個地方的商家合作,開始發放現金回饋,分別是 Bank -> Store 回饋 $70 、 Castle -> Shop 回饋 $30。
    1t6Wcvw

  • 跟昨天一樣,不知道到達的價格前都先設為無窮大,如果有比較便宜的價格再更新,這樣的行為稱為 Relaxation
    4AXbMiC

  • 跟昨天一樣,先從 Home 出發,出來後有兩條路,Home -> Bank 是 $150,Home -> Store 是 $50
    h4OIjno

  • 記性不好的灰姑娘趕快先寫上她的小本本~
    CA3WxTt

  • 再從 Home 可到達的地方隨機選一個點做延伸,下圖選擇了 Bank ,Bank 可延伸出兩條路徑與計算出價格,分別是 Home -> Bank -> Bar 的 $260 ( $150 + $ 110 ) 跟 Home -> Bank -> Store 的 $80 ( $150 - $70 )
    O2ey1k8

  • 再來更新小本本~因為 Home -> Bank -> Bar 的 $260 比無窮大小,所以更新原本的資料,而剛剛的 Home -> Bank -> Store 沒有比原本的小,所以不用更新
    BEFh4fE

  • 再挑一個點做延伸,這次挑 Stroe,分別延伸出 Home -> Store -> Castle $110 ( $50 + $60 ) 、 Home -> Store -> Shop $130 ( $50 + $80 )
    18Lof7q

  • 比對一下有沒有比較便宜,有得話就更新上去,沒有則維持不變
    CMHyGxB

  • 再選擇從 Castle 延伸的路,只有一條 Home -> Store -> Castle -> Shop 為 $80 ( $50 + $60 - $30 )
    8XQ1VpY

  • Home -> Store -> Castle -> Shop 的 $80 比原本 Home -> Store -> Shop 的 $130 還便宜,所以更新上去!
    YywQ79L

  • 最後從家裡出發到各個點最划算的路線,終於計算出來了!
    lP6DqiM

  • 剛剛前面有提到此演算法不能有負權環,是為何呢~假設今天開闢了一條免費的新道路 Castle -> Bank
    upXHvtq

  • 而 Bank -> Store -> Castle -> Bank 這樣一趟會為賺 $10 元,所以精打細算的灰姑娘就會在這邊繞到商家都破產為止 XDD ,所以千萬不能有負權環啊~ (所謂的負數圖示是用回饋金來代表,以灰姑娘要花多少錢的角度來看,是要扣掉回饋金)
    vPRNd9C

參考資料 :

維基百科 : 貝爾曼-福特演算法

演算法筆記 : Path

Single-Source Shortest Path:Bellman-Ford Algorithm


好啦~今天就先到這邊啦,感謝閱讀,換我來去嚕一下我家狗狗了!掰掰明天見~


上一篇
【在廚房想30天的演算法】Day 21 演算法 : 最短路徑 Shortest Path Dijkstra 演算法
下一篇
【在廚房想30天的演算法】Day 23 資訊安全與演算法 : 前言
系列文
少女人妻在廚房裡想不通的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言